package com.le.basic.Sort;

import java.util.Arrays;

/**
 * 给定一个数组，求如果排序之后，相邻两数的最大差值，
 * 要求时 间复杂度O(N)，且要求不能用非基于比较的排序
 */
public class Code_11_BucketSortMaxGap {

    public static int getGap(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int len = arr.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            min = Math.min(arr[i], min);
            max = Math.max(arr[i], max);
        }
        if (min == max) { // 数组只有一种元素
            return 0;
        }
        boolean[] hasNum = new boolean[len + 1]; // 标志桶是否有元素
        int[] maxs = new int[len + 1]; // 记录桶最大值
        int[] mins = new int[len + 1]; // 记录桶最小元素
        int bucketId = 0; // 决定放入那个桶
        for (int i = 0; i < len; i++) {
            bucketId = bucket(arr[i], len, min, max);
            mins[bucketId] = hasNum[bucketId] ? Math.min(mins[bucketId], arr[i]) : arr[i];
            maxs[bucketId] = hasNum[bucketId] ? Math.max(maxs[bucketId], arr[i]) : arr[i];
            hasNum[bucketId] = true;
        }
        int result = 0; // 存放最大差值
        int lastMax = maxs[0]; // 存放前一位置最大值
        for (int i = 1; i <= len; i++) {
            if (hasNum[i]) {
                result = Math.max(result, mins[i] - lastMax); // 后一个位置最小值减去前一位置最大值
                lastMax = maxs[i];
            }
        }
        return result;
    }

    /**
     * @param num 元素
     * @param len 数组长度
     * @param min 数组最小值
     * @param max 数组最大值
     * @return 放入桶的下标
     */
    private static int bucket(int num, int len, int min, int max) {
        return ((num - min) * len) / (max - min);
    }


    // for test
    public static int comparator(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int gap = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            gap = Math.max(nums[i] - nums[i - 1], gap);
        }
        return gap;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (getGap(arr1) != comparator(arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

}
